#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣139. 单词拆分
// 【难度】中等
// 【提交】 https://leetcode.cn/problems/word-break/submissions/675848778/
// 【标签】动态规划；字符串；哈希表
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // dp[i]表示字符串s的前i个字符能否被拆分成字典中的单词
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;  // 空字符串可以被拆分
        
        for (int i = 1; i <= s.size(); i++) {
            for (int j = 0; j < wordDict.size(); j++) {
                // 检查当前单词是否能匹配s的末尾部分
                if (i >= wordDict[j].size() && 
                    s.substr(i - wordDict[j].size(), wordDict[j].size()) == wordDict[j]) {
                    // 如果匹配成功，则当前状态取决于去掉这个单词后的状态
                    dp[i] = dp[i] || dp[i - wordDict[j].size()];
                }
            }
        }
        return dp[s.size()];
    }
};

/**
 * @brief 学习总结：
 * 本题是经典的字符串分割问题，使用动态规划解决。
 * 
 * 解题思路：
 * 1. 定义dp[i]表示s的前i个字符能否被拆分成字典中的单词
 * 2. 初始化dp[0]=true，表示空字符串可以被拆分
 * 3. 对于每个位置i，检查所有字典单词是否能匹配s的末尾
 * 4. 如果匹配成功，则dp[i]取决于去掉该单词后的状态
 * 
 * 算法分析：
 * - 时间复杂度：O(n*m*k)，其中n为s长度，m为字典大小，k为单词平均长度
 * - 空间复杂度：O(n)，dp数组的大小
 * 
 * 优点：
 * - 动态规划思路清晰，状态定义合理
 * - 代码实现简洁，逻辑正确
 * 
 * 缺点和改进建议：
 * 1. 时间复杂度较高，可以优化：
 *    - 使用哈希集合存储字典，快速判断单词是否存在
 *    - 内层循环遍历所有可能的单词结尾，而不是所有字典单词
 * 
 * 2. 优化后的版本：
 * 
 * bool wordBreak(string s, vector<string>& wordDict) {
 *     unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
 *     vector<bool> dp(s.size() + 1, false);
 *     dp[0] = true;
 *     
 *     for (int i = 1; i <= s.size(); i++) {
 *         for (int j = 0; j < i; j++) {
 *             if (dp[j] && wordSet.count(s.substr(j, i - j))) {
 *                 dp[i] = true;
 *                 break;
 *             }
 *         }
 *     }
 *     return dp[s.size()];
 * }
 * 
 * 3. 进一步优化：限制内层循环范围，只检查最大单词长度内的位置
 * 
 * 4. 考虑使用BFS或DFS的解法，在某些情况下可能更高效
 * 
 * 核心思想：
 * 动态规划是解决字符串分割问题的有效方法，关键在于找到合适的状态转移方程。
 * 本题的状态转移方程：dp[i] = ∃(dp[j] && wordSet.contains(s[j:i]))，其中0≤j<i
 * 
 * 应用场景：
 * - 单词拆分问题
 * - 字符串分割问题
 * - 词典匹配问题
 */